#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> getXY(int num, int n) {
    int x = n - 1 - (num - 1) / n;

    int y;
    if ((n - x) % 2) {
        y = (num - 1) % n;
    } else {
        y = n - 1 - (num - 1) % n;
    }
    return {x, y};
}

int snakesAndLadders(vector<vector<int>>& board) {
    int n = board.size();
    vector<bool> visited(n * n + 1, false);
    queue<pair<int, int>> q;
    q.push({1, 0});
    visited[1] = true;

    while (!q.empty()) {
        int frontPos = q.front().first;
        int frontStep = q.front().second;
        q.pop();

        for (int i = 1; i <= 6; i++) {
            int nxt = frontPos + i;
            if (nxt > n * n) {
                break;
            }

            int x = getXY(nxt, n)[0], y = getXY(nxt, n)[1];
            if (board[x][y] != -1) {
                nxt = board[x][y];
            }

            if (nxt == n * n) {
                return frontStep + 1;
            }

            if (!visited[nxt]) {
                visited[nxt] = true;
                q.push({nxt, frontStep + 1});
            }
        }
    }

    return -1;
}